package leetcode;

import java.util.PriorityQueue;
import java.util.Queue;

public class MedianFinder2 {

    //pq1:小根堆，保存较大的一半，且元素数量为奇数时，保存多一个
    //pq2:大根对，保存较小的一半，且元素数量为奇数时，保存少一个
    Queue<Integer> pq1, pq2;


    public MedianFinder2() {
        pq1 = new PriorityQueue<>();
        pq2 = new PriorityQueue<>((a, b) -> (b - a));
    }

    public void addNum(int num) {
        if (pq1.size() == pq2.size()) {
            pq2.offer(num);
            pq1.offer(pq2.poll()); //pq2吃一个，吐一个最大的给pq1,pq2数量不变，pq1数量+1
        }else {
            pq1.offer(num);
            pq2.offer(pq1.poll());//pq1吃一个，吐一个最小的给pq2,pq1数量不变，pq2数量增加1
        }
    }

    public double findMedian() {
        if (pq1.size() == pq2.size()) {
            return (pq1.peek() + pq2.peek()) / 2.0;
        }
        return pq1.peek();
    }

}
